Non-Uniform Rational B-Splines (NURBS) are industry standard tools for the representation and design of geometry. NURBS, as explained by Markus Altmann in “About Nonuniform Rational B-Splines—NURBS,” are used for a variety of reasons. They offer one common mathematical form for both standard analytical shapes (e.g., conics) and free-form shapes. NURBS provide the flexibility to design a large variety of shapes and can be evaluated reasonably fast by numerically stable and accurate algorithms. They are invariant under affine as well as perspective transformations and are generalizations of non-rational B-Splines and non-rational and rational Bezier curves and surfaces.
However, one of the drawbacks of NURBS is the need for extra storage to define traditional shapes (e.g., circles). This results from parameters in addition to the control points, but will allow the desired flexibility for defining parametric shapes. NURBS-shapes are not only defined by control points; weights, associated with each control point, are also necessary. A NURBS curve C(u), for example, which is a vector-valued piecewise rational polynomial function, may be defined as:
                              C          ⁡                      (            u            )                          =                                            sum              ⁡                              (                                                      i                    =                    0                                    ,                  n                                )                                      ⁢                          {                                                w                  i                                *                                  P                  i                                *                                  N                                      i                    ,                                          k                      ⁡                                              (                        u                        )                                                                                                        }                                                          sum              ⁡                              (                                                      i                    =                    0                                    ,                  n                                )                                      ⁢                          {                                                w                  i                                *                                  N                                      i                    ,                                          k                      ⁡                                              (                        u                        )                                                                                                        }                                                          (        1        )            where
wi=weights
Pi=control points (vector)
Ni,k=normalized B-spline basis functions of degree k.
The B-Splines are defined recursively as:
                              N                      i            ,                          k              ⁡                              (                u                )                                                    =                                                            u                -                                  t                  i                                                                              t                                      i                    +                    k                                                  -                                  t                  i                                                      *                          N                              i                ,                                  k                  -                                      1                    ⁢                                          (                      u                      )                                                                                                    +                                                    t                                  i                  +                  k                  +                  1                  -                  u                                                                              t                                      i                    +                    k                    +                    1                                                  -                                  t                                      i                    +                    1                                                                        *                          N                                                i                  +                  1                                ,                                  k                  -                                      1                    ⁢                                          (                      u                      )                                                                                                                              (        2        )            and/1, if ti<=u<ti+1 Ni,0(u)=<\0, elsewhere ti are the knots forming a knot vector andU={t0, t1, . . . , tm}.The Knot Vector
The knot vector uniquely determines the B-Splines as demonstrated above relative to equation (2). The relation between the number of knots (m+1), the degree (k) of Ni,k and the number of control points (n+1) is given by m=n+k+1.
The sequence of knots in the knot vector U is assumed to be non-decreasing, i.e., ti<=ti+1. Each successive pair of knots represents an interval [ti, ti+1) for the parameter values to calculate a segment of a shape.
For NURBS, the relative parametric intervals (not spans) need not be the same for all shape segments, i.e., the knot spacing is non-uniform, leading to a non-periodic knot vector of the form:U={a, . . . , a, tk+1, . . . , tm−k−1, b, . . . , b},  (3)where a and b are repeated with multiplicity of k+1. The multiplicity of a knot affects the parametric continuity at this knot. Non-periodic B-Splines, like NURBS, are infinitely and continuously differentiable in the interior of a knot span and k−M−1 times continuously differentiable at a knot, where M is the multiplicity of the knot. In contrast, a periodic knot vector U={0, 1, . . . , n} is everywhere k−1 times continuously differentiable. Considering the knot vector for NURBS, the end knot points (tk, tn+1) with multiplicity k+1 coincide with the end control points P0, Pn.
Since the knot spacing could be non-uniform, the B-Splines are no longer the same for each interval [ti, ti+1) and the degree of the B-Spline may vary. Considering the whole range of parameter values represented by the knot vector, the different B-Splines build up continuous (overlapping) blending functions Ni,k(u), as defined in equation (2), over this range of parameter values, which are illustrated in FIG. 11. These blending functions have the following properties:                1. Ni,k(u)>=0, for all i, k, u;        2. Ni,k(u)=0, if u not in [ti, ti+k+1), meaning local support of k+1 knot spans, where Ni,k(u) is nonzero;        3. If u in [ti, ti+1), the non-vanishing blending functions are Ni−k,k(u), . . . , Ni,k(u);        4. Sum (j=i−k, i) {Nj,k(u)}=sum(i=0, n) {Ni,k(u)}=1, (partition of unity); and        5. In case of multiple knots, 0/0 is deemed to be zero.        
The first and fourth properties, as illustrated in FIG. 12, together, result in a convex hull. The polyline of control points build up to a shape defined by a NURBS curve. The second and third properties illustrate that k+1 successive control points define a shape segment, and a control point is involved in k+1 neighboring shape segments. Therefore, changing a control point or weight influences just k+1 shape segments, defined over the interval given in equation (2).
Curve/Surface Definition
The previous definition of a NURBS-curve in equation (1) may be rewritten using rational basis functions:
                              R                      i            ,                          k              ⁡                              (                u                )                                                    =                                            w              i                        *                          N                              ik                ⁡                                  (                  u                  )                                                                                        sum              ⁡                              (                                                      j                    =                    0                                    ,                  n                                )                                      ⁢                          {                                                w                  j                                *                                  N                                      j                    ,                                          k                      ⁡                                              (                        u                        )                                                                                                        }                                                          (        4        )            into:C(u)=sum(i=0,n){Pi*Rl,k(u)}.  (5)
A NURBS-surface may be defined in a similar way:S(u,v)=sum(i=0,n)sum(j=0,m)Pi,j*Ri,k,j,l(u,v) where
                              R                      i            ,            k            ,            j            ,                          l              ⁡                              (                                  u                  ,                  v                                )                                                    =                                            w                              i                ,                j                                      *                          N                              i                ,                                  k                  ⁡                                      (                    u                    )                                                                        *                          N                              j                ,                                  l                  ⁡                                      (                    v                    )                                                                                                          sum              ⁡                              (                                                      r                    =                    0                                    ,                  n                                )                                      ⁢                          {                                                sum                  ⁡                                      (                                                                  s                        =                        0                                            ,                      m                                        )                                                  ⁢                                  {                                                            w                                              r                        ,                        s                                                              *                                          N                                              r                        ,                                                  k                          ⁡                                                      (                            u                            )                                                                                                                *                                          N                                              s                        ,                                                  l                          ⁡                                                      (                            u                            )                                                                                                                                }                                            }                                                          (        6        )            
The rational basis functions have the same properties as the blending functions. One point to emphasize, is their invariance under affine and (even) perspective transformations. Therefore, only the control points have to be transformed to get the appropriate transformation of the NURBS shape.
Computational Algorithm
NURBS can be evaluated effectively by using homogeneous coordinates. The following steps demonstrate one method to perform the evaluation:                1. Add one dimension to the control points (e.g., P=(x, y)−>P′(x, y, 1)) and multiply them by their corresponding weights, i.e., in 2D: Pi(xi, yi)−>Pi′(wi*xi, wi*yi, wi)        2. Calculate NURBS in homogeneous coordinates:C′(u)=sum(i=0,n){Pi′(u)*Ni,k(u)}        3. Map “homogeneous” NURBS back to original coordinate system with:        
                                          map            ⁡                          (                                                X                  ⁢                                                                          ⁢                  1                                ,                                  X                  ⁢                                                                          ⁢                  2                                ,                …                ⁢                                                                  ,                Xn                ,                W                            )                                =                                                                                          /                                          (                                                                        X                          ⁢                                                                                                          ⁢                                                      1                            /                            W                                                                          ,                                                  X                          ⁢                                                                                                          ⁢                                                      2                            /                            W                                                                          ,                        …                        ⁢                                                                                                  ,                                                  Xn                          /                          W                                                                    )                                                        ,                                                            if                      ⁢                                                                                          ⁢                      W                      ⁢                                                                                                                        ⁢                                                                                                                      ⁢                      not                                        =                    0                                                                                                      <                                                                                                          ∖                                          (                                                                        X                          ⁢                                                                                                          ⁢                          1                                                ,                                                  X                          ⁢                                                                                                          ⁢                          2                                                ,                        …                        ⁢                                                                                                  ,                        Xn                                            )                                                        ,                                                            if                      ⁢                                                                                          ⁢                      W                                        =                    0                                                                                      ⁢                                  ⁢                              C            ⁡                          (              u              )                                =                                    map              ⁡                              (                                                      C                    ′                                    ⁡                                      (                    u                    )                                                  )                                      =                                                            sum                  ⁡                                      (                                                                  i                        =                        0                                            ,                      n                                        )                                                  ⁢                                  {                                                            w                      i                                        *                                          P                      i                                        *                                          N                                              i                        ,                                                  k                          ⁡                                                      (                            u                            )                                                                                                                                }                                                                              sum                  ⁡                                      (                                                                  i                        =                        0                                            ,                      n                                        )                                                  ⁢                                  {                                                            w                      i                                        *                                          N                                              i                        ,                                                  k                          ⁡                                                      (                            u                            )                                                                                                                                }                                                                                        (        7        )            For u in [ti, ti+1), the only existing blending functions to consider in evaluation of the curve at U are Ni−k,k(u), . . . , Ni,k(u). An effective algorithm for the computation of the non-vanishing blending functions is described in C. deBoor, “A Practical Guide to Splines,” 1978, New York, Springer-Verlag.The Weights
As mentioned above, changing the weight wi of a control point Pi affects only the range [ti, ti+k+1) (in case of a curve). The geometric meaning of the weights is illustrated in FIG. 13.
Defining the points:B=C(u;wi=0);N=C(u;wi=1); andBi=C(u;winot={0,1}).N and Bi can also be expressed as:N=(1−a)*B+a*Pi Bi=(1−b)*B+b*Pi,wherea=Ri,k(u;wi=1)b=Ri,k(u).The following identity is obtained from the expression of a and b:(1−a)/a:(1−b)/b=PiN/BN:PiBi/BBi=wi,which is called the cross- or double ratio of the four points Pi, B, N, Bi. From these expressions, the effect of shape modification can be derived:                Bi sweeps out on a straight line segment;        If wi=0 then Pi has no effect on shape;        If wi increases, so b and the curve is pulled toward Pi and pushed away from Pj, for j not=i;        If wi decreases, so b and the curve is pushed away from Pi and pulled toward Pj, for j not=i ; and        If wi−>infinity then b−>1 and Bi−>Pi, if u in [ti, ti+k+1)The Problem        
Various techniques have been attempted for creating a NURBS surface in different fields of art. For example, International Publication No. WO 02/37422, and U.S. Pat. No. 6,765,570, incorporated herein by reference, propose various techniques for the manual generation of editable (NURBS) surfaces used in analyzing and interpreting seismic events. Other conventional applications propose creating an editable (NURBS) surface using interpolation techniques well known in the art. Such techniques may be referred to as an “exact-fit” approach to determining the editable surface. An exact-fit approach is more likely to render a less uniform, if not non-uniform, editable surface as compared to a “best-fit” approximation of the editable surface. Moreover, the exact-fit approach to defining an editable NURBS surface may be impractical, if not cost prohibitive, for large 3D data sets often encountered in the analysis of seismic data.
Other conventional methods for converting unordered points to surfaces are generally described in Shepard, D., “A two dimensional interpolation function for irregular spaced data,” 1968, pp. 517-524, Proceedings 23rd ACM National Conference. One well-known method for interpolating scattered points, defines a surface value based on given points and weight functions. Although the result is relatively rough, the fundamental idea has inspired many other methods.
Another well-known method, generally referred to as the “Thin Plate Spline” method has been incorporated in medical imaging applications and is capable of precisely guiding the target surface such that it passes through all given points. See Hardy, R. L. Desmarrais, R.N., “Interpolation using surface spline,” 1972, pp. 189-197, Journal of Aircraft 9 and Dyn, N., “Interpolation in Scattered Data by Radial Functions,” 1987, pp. 47-61, In Chui, C. K.; Schumaker, L. L.; Ultreres, F. I. (ed) Topics in Multivariate Approximation. However, this technique requires the inversion of large matrices, which is computationally expensive and generally impractical for a large number of input points that may only require a best-fit approximation.
Another conventional method for converting a point cloud to a surface is described in Hoppe, H., et al., “Surface Reconstruction from Unorganized Points, 1992, pp. 71-78, Comput. Graph. 26. However, this method assumes that the input points are evenly distributed over the entire domain, which is also impractical for input points that are densely populated in some areas and non-existent in other areas.
A need therefore, exists for automatically approximating an editable surface from a 3D data set or 3D point set comprising a large volume of unordered and/or unstructured data points, which may be imaged in the form of an editable NURBS surface.